競プロ典型 90 問 016
(工事中)
解き方
解答例
下は上記の方法で解いたときの提出結果である。また、その提出の際に提出したソースコードをその下に転記する。
code: C
int gcd(int a, int b, int *x, int *y) {
int ans = 0;
int tmp = 0;
if (a < b) {
return gcd(b ,a, y, x);
}
if (b < 2 || a % b == 0) {
*x = 0;
*y = 1;
return b;
}
ans = gcd(b, a % b, x, y);
tmp = *x;
*x = *y;
*y = tmp - (a / b) * *y;
return ans;
}
int main () {
int n = 0;
int res = 0;
int ans = 10000;
int gcd_ab = 0;
int ka = 0;
int kb = 0;
int lcm = 0;
int max_c = 10000;
res = scanf("%d", &n);
res = scanf("%d", c);
res = scanf("%d", c+1);
res = scanf("%d", c+2);
}
}
}
for (int i = 0; i < 3; i++) {
for (int j = i; j < 3; j++) {
int dummy_x = 0;
int dummy_y = 0;
int gcd_ij = gcd(ci, cj, &dummy_x, &dummy_y); }
}
gcd_ab = gcd(c0, c1, &ka, &kb); if (ka < 0) {
int k = 1 + (-ka) / trans01; } else {
}
if (max_c > n / c2 + 1) { }
for(int i = 0; i < max_c; i++) {
if (n % gcd_ab == 0) {
long long tmp_ka = ((long long) ka) * ((long long) (n / gcd_ab));
long long tmp_kb = ((long long) kb) * ((long long) (n / gcd_ab));
if (tmp_ka < 0) {
long long k = 1 + (-tmp_ka) / ((long long) trans01); tmp_ka += k * ((long long) trans01); tmp_kb -= k * ((long long) trans10); } else {
int k = tmp_ka / ((long long) trans01); tmp_ka -= k * ((long long) trans01); tmp_kb += k * ((long long) trans10); }
if (tmp_kb >= 0 && ans > tmp_ka + tmp_kb + max_c-i-1) {
ans = tmp_ka + tmp_kb + max_c-i-1;
}
}
}
printf("%d\n", ans);
return 0;
}
私の提出一覧
table: submissions_atcoder_typical90_016
提出のURL 提出時刻 結果 備考
感想
この問題以降については、ローカルにおいてあったzakkan.txt（雑感）にまだ書かれていない。
特にローカルのファイルを今後更新する必要もないため、今後はこちらに書く
まだちゃんと途中経過の提出を見ていないので、なぜこの問題は提出回数が多いのか確認できていない。
それ以前に、あまり覚えていないかな。
ただ、正解した提出を見る限り、拡張ユークリッドの互除法を使っているので、まだ慣れない中、$ 1 足したり引いたりの調整がなかなかうまく行かなくて手間取ったのかな
ところで、解説をみたけれど、やはりこの問題は拡張ユークリッドの互除法要らなかったよね。
ところで、解説を読んだけれど、やはりこの問題に拡張ユークリッドの互除法は要らなかったよね。
たぶん、この制約で2乗のオーダーは微妙かなと思って、そうしたのかな。2乗がだめと思ったのか、3乗がだめと思ったのか微妙かな？